class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        adj = {}
        adj['a'] = ['b', 'c']
        adj['b'] = ['a', 'c']
        adj['c'] = ['a', 'b']
        a = 2**(n - 1)
        b = a + 2**(n - 1)
        c = b + 2**(n - 1)
        string = None
        if k <= a:
            string = 'a'
        elif k <= b:
            string = 'b'
            k -= a
        elif k <= c:
            string = 'c'
            k -= b
        if string is None:
            return ''
        n -= 1
        while n > 0:
            left = 2**(n - 1)
            if k <= left:
                string += adj[string[-1]][0]
            else:
                string += adj[string[-1]][1]
                k -= left
            n -= 1

        return string
